﻿#include<math.h>
#include<time.h>
#include<vector>
#include<algorithm>
#include"Ai.h"

using namespace std;

Ai::Ai(){
    searchTime = 0.01;       //表示搜索的时间，更大的搜索时间表示更深的搜索，单位s
    smoothWeight = 0.1;   //平滑度权重
    monoWeight = 1.0;     //单调性权重
    emptyWeight = 2.7;    //空余格子数量权重
    maxWeight = 1.0;      //最大值权重
}

/* Function:search
 * Summary:α-β剪枝，深度优先搜索。
 * Input:
 *      arr:int**类型，棋盘数据，arr[4][4]
 *      depth:int,搜索深度，搜索深度为0时返回对应状态的评估
 *      alpha:double,子状态中下限的最大值
 *      beta:double,子状态中上限的最小值
 *      cutoffs:bool,是否剪枝，true为剪枝
 *      playerTurn:bool,游戏当前回合的行动者，true为玩家，false为电脑
 * Output:MoveResult，当前状态下最好的移动策略，包含评估的分数、移动方向和剪枝信息
 */
MoveResult Ai::search(int **arr, int depth, double alpha, double beta, bool cutoffs, bool playerTurn){
    double bestScore;
    int bestMove = 0;
    MoveResult result,temp;

    //clog << "playerTurn" << playerTurn << "\n";
    //玩家回合
    if(playerTurn){
        bestScore = alpha;
        for(int direction = 1; direction <= 4; direction++){
            //int **newArr;
            int **newArr,**tempArr;
            newArr = (int **)malloc(sizeof(int*)*4);
            for(int i = 0; i < 4 ; i++)
                newArr[i] = (int *)malloc(sizeof(int)*4);
            cloneGrid(newArr,arr);

            Game newData(newArr);
            //如果该移动时有效的
            //clog << "direciton: " << direction<<"\n";
            if(newData.moveAI(direction)){
                //判断游戏是否结束
                if(newData.gameOver()){
                    //clog  << "depth: "<< depth <<
                    //        "direciton: " << direction << "\n" ;
                    result.moveDirction = direction;
                    result.score = 10000;
                    result.cutoffs = cutoffs;
                    for(int j = 0; j < 4 ; j++)
                        free(newArr[j]);
                    free(newArr);
                    return result;
                }
                tempArr = newData.getData();

                if(depth == 0){
                    temp.moveDirction = direction;
                    temp.score = this->eval(tempArr);
                }
                else{
                    temp = search(tempArr, depth-1, bestScore, beta, cutoffs, false);
                    if(temp.score > 9900){
                        temp.score--;
                    }
                    cutoffs = temp.cutoffs;
                }
                //clog << "temp direciton: " << temp.moveDirction << " score: " << temp.score << "\n";
                if(temp.score > bestScore){
                    bestScore = temp.score;
                    bestMove = direction;
                }
                if(bestScore > beta){
                    cutoffs = true;
                    result.moveDirction = bestMove;
                    result.score = beta;
                    result.cutoffs = cutoffs;
                    for(int j = 0; j < 4 ; j++)
                        free(newArr[j]);
                    free(newArr);
                    return result;                    
                }
            }

            for(int j = 0; j < 4 ; j++)
                free(newArr[j]);
            free(newArr);
        }
    }
    else{   //电脑回合
        bestScore = beta;

        //两行数值,第一行储存插入2时的评价值，第二行储存插入4时的评价值
        double insertValue[2][16]={{0}};

        //储存每个插入位置的值
        for(int x = 0; x < 4; x++){
            for(int y = 0; y < 4; y++){
                if(arr[x][y] == 0){
                    arr[x][y] = 2;
                    insertValue[0][x*4+y] = - smoothness(arr) + islands(arr);
                    arr[x][y] = 4;
                    insertValue[1][x*4+y] = - smoothness(arr) + islands(arr);
                    arr[x][y] = 0;
                }
            }
        }

        //找到最大值并记录位置
        double max = 0;
        vector<int> location;

        for(int x = 0; x < 2; x++)
            for(int y = 0; y < 16; y++)
                max = (max < insertValue[x][y]) ? insertValue[x][y] : max;
      
        for(int x = 0; x < 2; x++)
            for(int y = 0; y < 16; y++)
                if(max == insertValue[x][y])
                    location.push_back(x*16+y);
                                 
        //对于这些电脑可能会生成的最麻烦的位置进行搜索
        for(unsigned i = 0; i < location.size(); i++){
            //int **newArr = cloneGrid(arr);
            int **newArr;
            newArr = (int **)malloc(sizeof(int*)*4);
            for(int j = 0; j < 4 ; j++)
                newArr[j] = (int *)malloc(sizeof(int)*4);
            cloneGrid(newArr,arr);

            if(location[i]/16 == 0) //插入2
                newArr[location[i] % 16 / 4][location[i] % 16 % 4] = 2;
            else    //插入4
                newArr[location[i] % 16 / 4][location[i] % 16 % 4] = 4;
        
            //Game newData(newArr);

            temp = search(newArr, depth, alpha, bestScore, cutoffs, true);
            cutoffs = temp.cutoffs;

            if(temp.score < bestScore){
                bestScore = temp.score;
            }
            if(bestScore < alpha){
                cutoffs = true;
                result.moveDirction = 0;
                result.score = alpha;
                result.cutoffs = cutoffs;
                for(int j = 0; j < 4 ; j++)
                    free(newArr[j]);
                free(newArr);
                return result;                   
            }

            for(int j = 0; j < 4 ; j++)
                free(newArr[j]);
            free(newArr);
        }

    }
    

    result.moveDirction = bestMove;
    result.score = bestScore;
    result.cutoffs = cutoffs;
    return result;  
}

/* Function:stepAi
 * Summary:调用单步优化算法，得到下一步提示
 * Input:
 *     arr:int**类型，棋盘数据，arr[4][4]
 * Output:输出为下一步的方向，1,2,3,4分别表示上下左右
 */
int Ai::stepAi(int **arr){
    MoveResult result;

    result = iterativeDeep(arr);


    return result.moveDirction;
    //return 1;
}

/* Function:iterativeDeep
 * Summary:使用深度优先搜索，搜索可能的情况并进行剪枝
 * Input:
 *     arr:int**类型，棋盘数据，arr[4][4]
 * Output:MoveResult，包含对应的分数、移动方向和剪枝信息
 */
MoveResult Ai::iterativeDeep(int **arr){
      
    int depth = 0;
    MoveResult result,temp;
    clock_t start;

    start = clock();

    do{
        temp = search(arr,depth,-10000,10000,false,true);
        if(temp.moveDirction == 0){
            break;
        }
        else{
            result = temp;
        }
        //clog << "depth: "<< depth <<
        //        " direciton: " << result.moveDirction <<
        //       " score: " << result.score << "\n" ;
        depth++;
    }while(((clock() - start)/CLOCKS_PER_SEC) < searchTime);

    return result;
    
}

/* Function: eval
 * Summary: 评价函数，对棋盘状态进行评价。得分越高则越有价值，越能接近胜利。
 * Input: 
 *      arr:int**,棋盘数据arr[4][4]
 * Output: 得分值，类型为double
 */
double Ai::eval(int **arr){
    return  emptiness(arr) * emptyWeight +
            monotonicity(arr) * monoWeight +
            smoothness(arr) * smoothWeight +
            maxValue(arr) * maxWeight;
}


/* Function: emptiness
 * Summary: 评价空旷度，启发函数之一。空的格子越多，说明该情况越有价值。
 * Input: 
 *      arr:int**,棋盘数据arr[4][4]
 * Output: 得分值，类型为double
 */
double Ai::emptiness(int **arr){
    int emptiness = 0;
    for(int x = 0; x < 4; x++){
        for(int y = 0; y < 4; y++){
            if(arr[x][y] == 0)
                emptiness++;
        }
    }

    return emptiness != 0 ? log(emptiness) : 0;
}

/* Function: smoothness
 * Summary: 评价顺滑度，启发函数之一。相邻块之间的值越接近，价值越高。
 * Input: 
 *      arr:int**,棋盘数据arr[4][4]
 * Output: 得分值，类型为double
 */
double Ai::smoothness(int **arr){
    double smoothness = 0;
    double value,targetValue;
    for(int x = 0; x < 4; x++){
        for(int y = 0; y < 4; y++){
            if(arr[x][y] != 0){
                value = log(arr[x][y])/log(2);
                //只计算右和下
                if(overBound(x+1,y) && arr[x+1][y] != 0){
                    targetValue = log(arr[x+1][y])/log(2);
                    smoothness -= abs(value - targetValue);
                }
                if(overBound(x,y+1) && arr[x][y+1] != 0){
                    targetValue = log(arr[x][y+1])/log(2);
                    smoothness -= abs(value - targetValue);
                }
            }
        }
    }
    return smoothness;
}

/* Function: maxValue
 * Summary: 评价格子中的最大数，启发函数之一。格子中最大的值越大，价值越高。
 *          希望算法能够寻找合成更大的数。
 * Input: 
 *      arr:int**,棋盘数据arr[4][4]
 * Output: 得分值，类型为double
 */
double Ai::maxValue(int **arr){
    int max = 0;
    for(int x = 0; x < 4; x++){
        for(int y = 0; y < 4; y++){
            if(max < arr[x][y])
                max = arr[x][y];
        }
    }
    return log(max)/log(2);    
}

/* Function: monotonicity
 * Summary: 评价棋盘的单调性，启发函数之一。棋盘沿一方向（上下左右）越单调，价值越高。
 *          便于更大数的合成。
 * Input: 
 *      arr:int**,棋盘数据arr[4][4]
 * Output: 得分值，类型为double
 */
double Ai::monotonicity(int **arr){
    double grade[4] = {0};
    double value,targetValue;
    //左右方向
    for(int x = 0; x < 4 ; x++){
        int col = 0;
        int nextCol = 1;
        while(nextCol < 4){
            while(nextCol < 4 && arr[x][nextCol] == 0){
                nextCol++;
            }
            if(nextCol >= 4){nextCol--;}

            value = (arr[x][col] != 0) ? log(arr[x][col])/log(2) : 0;
            targetValue = (arr[x][nextCol] != 0) ? log(arr[x][nextCol])/log(2) : 0;

            if(value > targetValue)
                grade[0] += targetValue-value;
            else
                grade[1] += value-targetValue;
            
            col = nextCol;
            nextCol++;
        } 
    }

    //上下方向
    for(int y = 0; y < 4 ; y++){
        int row = 0;
        int nextRow = 1;
        while(nextRow < 4){
            while(nextRow < 4 && arr[nextRow][y] == 0){
                nextRow++;
            }
            if(nextRow >= 4){nextRow--;}

            value = (arr[row][y] != 0) ? log(arr[row][y])/log(2) : 0;
            targetValue = (arr[nextRow][y] != 0) ? log(arr[nextRow][y])/log(2) : 0;

            if(value > targetValue)
                grade[2] += targetValue-value;
            else
                grade[3] += value-targetValue;
            
            row = nextRow;
            nextRow++;
        } 
    }

    return max(grade[0],grade[1]) + max(grade[2],grade[3]);
}

/* Function: islands
 * Summary: 评价棋盘的中块的多少，启发函数之一。相同数值且相邻的格子为同一块。
 *          块越多越难移动。
 * Input: 
 *      arr:int**,棋盘数据arr[4][4]
 * Output: 得分值，类型为double
 */
double Ai::islands(int **arr){
    int mark[4][4] = {{0}};
    double islands = 0;

    for(int x = 0; x < 4; x++){
        for(int y = 0; y < 4; y++){
            if(arr[x][y] == 0)
                mark[x][y] = -1;
        }
    }

    for(int x = 0; x < 4; x++){
        for(int y = 0; y < 4; y++){
            if(arr[x][y] != 0 && mark[x][y] == 0){
                islands++;
                markGrid(arr,mark,x,y,arr[x][y]);
            }
        }
    }
    return islands;

}

/* Function: markGrid
 * Summary: 类聚标记函数,如果两个格子相邻且值相等则为同一类
 * Input: 
 *      arr:int**,棋盘数据arr[4][4]
 *      mark:int(*)[4],二维数组,标记数组,1为已标记,0为未标记,-1为原值为0不用标记
 *      x:int,横坐标
 *      y:int,纵坐标
 *      value:int,类聚的值
 * Output: 无
 */
void Ai::markGrid(int **arr, int mark[][4],int x, int y, int value){
    if(overBound(x,y) && arr[x][y] == value && mark[x][y] == 0){
        mark[x][y] = 1;
        markGrid(arr,mark,x+1,y,value);
        markGrid(arr,mark,x-1,y,value);
        markGrid(arr,mark,x,y+1,value);
        markGrid(arr,mark,x,y-1,value);
    }
}


/* Function: overBound
 * Summary: 内联函数，判断坐标是否出界
 * Input: 
 *      x:int,横坐标
 *      y:int,纵坐标
 * Output: bool类型，true代表未出界
 */
inline bool Ai::overBound(int x,int y){
    return x>=0&&x<4&&y>=0&&y<4;
}

/* Function: cloneGrid
 * Summary: 克隆二维数组，并返回一个新的指针
 * Input: 
 *      arr:int**,棋盘数据arr[4][4]
 * Output: int**，二维数组指针
 */
void Ai::cloneGrid(int**newGrid,int **arr){

    for(int x = 0; x < 4; x++){
        for(int y = 0; y < 4; y++){
            newGrid[x][y] = arr[x][y];
        }
    }
    //return newGrid;
}
